From: Ian Buck
Sent: Thursday, October 11, 2001 3:11 PM
To: Bill Dally
Cc: lance@leland.Stanford.EDU; ujk@leland.Stanford.EDU;
Billmark@lambert.stanford.edu; horowitz@chroma.stanford.edu;
hanrahan@graphics.stanford.edu
Subject: RE: Brook - retained state


 So as Bill mentioned, I would like to allow a Reduction type
 operation.  Basically, each kernel has a return value and you can use
 that value to gather information at the granularity of the entire
 stream.

  For example if you wanted to know the largest value in a stream, one
  could write a kernel which would return the value of the stream
  (perhaps doing some transformations as well), and the return value
  would be processed by the reduction operator "max".

  Stream blah;
  float maxvalue;

  maxvalue = max RandomKernel(blah);

  From a language standpoint, I think this is fairly straightforward
  but is not flawless.

  - Do we limit all the reduction operators to associative operations
    only, like max, sum, average?  This helps a lot in parallel
    reductions however it may limit what you can do.

  - Allowing only a native return type (float, vec3f, etc.) is a bit
    limiting.  What if I wanted the largest stream element in a stream
    based on a field within that element?  I.e. A stream of fragments
    each having color, alpha, depth, and I want to know the alpha of
    the fragment with the largest depth.  What are the right semantics
    for this?  Key/Value pair?  Or what if I wanted the average color,
    alpha, and depth?  Do I have to pass over the data three times?

  - Finally, Reductions are big roadblocks to scalability.  Stream
    blah has to be completely processed before maxvalue can be used.
    There maybe cases where we want reductions on a smaller
    granularity than an entire stream.  This gets back to the
    discussion of allowing streams of streams, which means having
    kernels which spawn other kernels.

  Ian.


> -----Original Message-----
> From: Bill Dally [mailto:billd@csl.stanford.edu]
> Sent: Wednesday, October 10, 2001 9:40 PM
> To: Ian Buck
> Cc: lance@leland.Stanford.EDU; ujk@leland.Stanford.EDU;
> Billmark@lambert.stanford.edu; horowitz@chroma.stanford.edu;
> hanrahan@graphics.stanford.edu
> Subject: Brook - retained state
> 
> 
> Ian,
> 
> Nice job on the Brook language definition so far.  I like the idea of 
> moving the template declaration to the argument list.
> 
> A major difference between Brook and StreamC or my "generalized streams" 
> proposal is the lack of retained state in kernels between stream 
> elements.  Since you have no explicit in ">>" operator the kernel starts 
> "fresh" with each input element.
> 
> With this approach, how do you handle kernels that need to communicate 
> retained values between stream elements?  A simple example would be a 
> kernel that sums a list of numbers.  More complex examples include things 
> like sort, merge, and the composite kernel in the Imagine renderer.
> 
> ----Bill
> --------------------------------------------------------------------------
> Bill Dally                billd@csl.stanford.edu             (650)725-8945
> Professor of Electrical Engineering and Computer Science  FAX(650)725-6949
> Computer Systems Laboratory, Stanford University
> Gates Room 301
> Stanford, CA  94305                         http://csl.stanford.edu/~billd
> --------------------------------------------------------------------------
>